import com.sun
        .deploy
        .util
        .ArrayUtil;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 *
 * @author shilinghuai
 * @create 2022/4/1
 * @since 1.0.0
 */
public class Sort {
    //冒泡排序
    public static int[] bubblingSrot(int[] ia){//两两比较，每轮排出最后一个最大的数。
        for(int index=0;index<ia.length-1;index++){//第一层控制轮数
            int tmp = 0;
            for(int ib=tmp;ib<ia.length-index-1;ib++){//第二层控制两两比较
                //两两比较，如果前者大于后者，则需要调换一下
                if(ia[ib]>ia[ib+1]){
                    int tmpStroe= ia[ib+1];
                     ia[ib+1] = ia[ib];
                     ia[ib] = tmpStroe;
                }
            }
        }
        return ia;
    }
    //选择排序
    public static int[] choiceSort(int[] ia){
        for(int index=0;index<ia.length-1;index++){
            int tmp = index;
            for(int ib=index+1;ib<ia.length;ib++){
                if(ia[tmp]>ia[ib]){
                    int tmpStore = ia[ib];
                    ia[ib] = ia[index];
                    ia[index] = tmpStore;
                }
            }
        }
        return ia;
    }
    //归并排序(分治)代码有点像二叉树的遍历 start
    public static int[]  mergeSort(int[] ia){
        recursion(ia,0,ia.length/2-1);
        //合并
        recursion(ia,ia.length/2,ia.length-1);

        twoSort(ia,0,ia.length-1);
        return ia;
    }
    public static void recursion(int[] ia,int left,int right){
        if(left==right-1|| left == right+1){
           twoSort(ia,left,right);
            return;
        }
        //
        recursion(ia,left,(left+right)/2);

        recursion(ia,(left+right)/2+1,right);
        twoSort(ia,left,right);
    }
    public static void twoSort(int[] ia,int left,int right){
        if(left==right-1){
            if(ia[right]<ia[left]){
                int tmpSpecial = ia[left];
                ia[left] = ia[right];
                ia[right ] = tmpSpecial;
            }
            return;
        }
        int leftIndex = left;
        int leftEnd = (left+right)/2;
        int rightIndex = (left+right)/2+1;
        int[] tmp = new int[right-left+1];
        int tmpIndex =0;
        while (leftIndex<=leftEnd && rightIndex<=right ){
            if(ia[rightIndex]<ia[leftIndex]){//如果右边的数小于左边的数。右边的数进临时数组。指针右移。
                tmp[tmpIndex++] = ia[rightIndex++];
            }else {//如果右边的数大于左边的数。左边的数进临时数组，指针右移。
                tmp[tmpIndex++] = ia[leftIndex++];
            }
        }
        //判断是左边处理完了，还是右边处理完了。
        //如果是左边处理完了，右边的数据追加到临时数组后面。
        //如果是右边数据处理完了。左边的数据追加到临时数组后面。
        if(leftIndex==leftEnd+1){
            while (right>=rightIndex){
                tmp[tmpIndex++]= ia[rightIndex++];
            }
        }
        if(rightIndex == right+1){
            while (leftEnd>=leftIndex){
                tmp[tmpIndex++]= ia[leftIndex++];
            }
        }
        //临时数组和正式数组进行替换
        int replaceIndex = 0;
        int leftTmpIndex = left;
        while (tmp.length-1>=replaceIndex){
                ia[leftTmpIndex++] = tmp[replaceIndex++];
        }
    }
    //归并排序end
    //快速排序start（未验证）

    // 5,4,6,2,1
    //1,4,2,5,6    3


    public static void fastRecuision(int[] ia,int start,int end){

        int index = dugSrot(ia,start,end);
        if(index-start>=2)
        fastRecuision(ia,start,index-1);
        if(end-index>=2)
        fastRecuision(ia,index+1,end);
    }
    //5.4,6,2,1  1,4   √5
    //1,4,6,2,_  1,3    √6
    //1,4,_,2,6  2,3     √2
    //1.4.2，_,6  2 =2


    //5,4,3,2,1      1,4  √1
    //1,4,3,2,_      1,3   索引1,2,3，都不符合


    //1,2,3,4,5     1,4  √1
    //_,2,3,4,5      1,

    //默认取第一个数进行排序，默认第一个坑是第一个数，后续都是和第一个数进行比较
    //声明一个变量记录坑的位置
    //如果左右指针碰撞了，就停止。没有碰撞就进行挖坑，填上一个坑的操作。
    public static int dugSrot(int[] ia,int start,int end){
        int tmp = ia[start];
        int dug =start;
        start = start+1;
        while (start<=end){
            //一轮正好是先从后往前，再从前往后。
            while (ia[end]>tmp&&start<=end){                //先从后往前,找到小于目标的挖出来填到前一个坑
                end--;
            }
            if(start<=end&&ia[end]<tmp){
                ia[dug] = ia[end];
                dug = end;
                end--;
            }

            while (ia[start]<tmp&&start<=end){
                start++;

            }
            if(start<=end&&ia[start]>tmp){
                ia[dug] = ia[start];
                dug = start;
                start++;
            }

        }
        ia[dug]= tmp;
        return dug;
    }

    //快速排序end
    //归并排序2022/05/26START
    public static int[] mergeSortSecend(int[] ia){
        detailMerge(ia,0,(0+ia.length-1)/2);
        detailMerge(ia,(0+ia.length-1)/2+1,ia.length-1);
        twoSort(ia,0,ia.length-1);
        return null;
    }
    public static void detailMerge(int[] ia,int left,int right){
        if(left==right-1){
            twoSort(ia,left,right);
            return;
        }
        detailMerge(ia,left,(left+right)/2);
        detailMerge(ia,(left+right)/2,right);
        twoSort(ia,left,right);
    }
    //调用栈：以0,1,2,3,4,5,6,7为例.8-15类似
    //detailMerge(0,7)
    //    detailMerge(0,3)
    //        detailMerge(0,1)
    //        detailMerge(2,3)
    //        twoSort(0,3)
    //    detailMerge(4,7)
    //         detailMerge(4,5)
    //         detailMerge(5,7)
    //         twoSort(4,7)
    //

    //归并排序2022/05/26END
    //快速排序2022/05/26START

    //快速排序2022/05/26END
    //归并排序2022/05/27START

    //对5,4,6，7,3，2,1,0进行排序
    public static void mergeSortThrid(int[] ia,int start,int end){
        if(end-start<=1){
            twoSortThrid(ia,start,end);
            return;
        }
        mergeSortThrid(ia,start,(start+end)/2);
        mergeSortThrid(ia,(start+end)/2+1,end);
        twoSortThrid(ia,start,end);
    }
    //
    public static void twoSortThrid(int[] ia,int start,int end){
            //左右指针
            //右指针的数和左指针的数进行比较，谁比较小放到另外一个开辟的数组中。同时指针右移。
        //继续比较
        //判断那边的数据处理完了，在把没处理完的数据全部放到临时数组中
        //临时数组覆盖原数组
        //最后处理一下两个数据的情况
        //首先处理一下两个元素的情况
        if(end-start<=1){
            if(ia[start]>ia[end]){
                int tmpMy = ia[start];
                ia[start] = ia[end];
                ia[end] = tmpMy;
            }
            return;
        }
        int[] tmp = new int[end-start+1];//开辟临时数组
        int tmpIndex = 0;//声明临时数组的下标
        int leftEnd = (start+end)/2;//声明左边数组的终点
        int rightStart = (start+end)/2+1;//声明右边数组的起点
        int leftIndex = start;//声明左边数组的下标
        int rightIndex = rightStart;//声明右边数组的下标
        while (leftIndex<=leftEnd&&rightIndex<=end){
            if(ia[rightIndex]<ia[leftIndex]){
                tmp[tmpIndex++] = ia[rightIndex];
                rightIndex++;

            }else {
                tmp[tmpIndex++] = ia[leftIndex];
                leftIndex++;
            }
        }
        //判断哪边数组到达了尽头
        if(leftIndex >=leftEnd){//左边的数组到达了尽头
            while (tmpIndex<tmp.length){
                tmp[tmpIndex++] = ia[rightIndex++];
            }
        }else {
            while (tmpIndex<tmp.length){
                tmp[tmpIndex++] = ia[leftIndex++];
            }
        }
        //临时数组覆盖原数组
        int itmp = 0;
        for(int iaa =start;iaa<=end;iaa++){
            ia[iaa] = tmp[itmp++];
        }
    }
    //归并排序2022/05/27END


        //冒泡排序：两两比较，如果右边小于左边的数就进行调换，这样一轮下来就排好了末尾的最大的一个数。使用双循环实现。
        //选择排序：第一个数和后续的所有的数进行一一比较。如果这个数大于后面的数，则进行调换。这样一轮下来就排好了第一个最小的数。使用双循环实现。
        //冒泡排序的实现
        public static void budSort(int[] ia){
            for(int iaa=ia.length-1;iaa>0;iaa--){
                for(int ibb = 0;ibb<iaa;ibb++){
                    if(ia[ibb+1]<ia[ibb]){
                        int tmp = ia[ibb+1];
                        ia[ibb+1]= ia[ibb];
                        ia[ibb] = tmp;
                    }
                }
            }
        }
        public static void choiceSortSecond(int[] ia){
            for(int iaa=0;iaa<ia.length-1;iaa++){
                for(int ibb=iaa+1;ibb<ia.length;ibb++){
                    if(ia[iaa]>ia[ibb]){
                        int tmp = ia[iaa];
                        ia[iaa] =ia[ibb];
                        ia[ibb] = tmp;
                    }
                }
            }
        }

    //归并排序20220530START
    //递归
    public static void dec(int[] ia,int start,int end){
        if(end-start<=1){
            decSort(ia,start,end);
            return;
        }
        dec(ia,start,(start+end)/2);
        dec(ia,(start+end)/2+1,end);
        decSort(ia,start,end);
    }
    //排序
    public static void decSort(int[] ia,int start,int end){
        //声明左右指针，开辟新数组。
        int leftIndex = start;
        int leftEnd = (start+end)/2;
        int rightIndex = (start+end)/2+1;
        int[] tmpArray = new int[end-start+1];
        int tmpIndex = 0;
        //左右指针进行比较
        while(leftIndex<=leftEnd&&rightIndex<=end){
            if(ia[leftIndex]<ia[rightIndex]){
                tmpArray[tmpIndex++] = ia[leftIndex++];
            }else {
                tmpArray[tmpIndex++] = ia[rightIndex++];
            }
        }
        //判断哪个指针到末尾了
        if(leftIndex>leftEnd){
            //右边数组没有处理完
            while(rightIndex<=end){
                tmpArray[tmpIndex++]= ia[rightIndex++];
            }
        }else {
            while (leftIndex<=leftEnd){
                tmpArray[tmpIndex++] = ia[leftIndex++];
            }
        }
        //将临时数组覆盖数组
        int tmpIndexWhrite = 0;
        int startTmp = start;
        while (tmpIndexWhrite<tmpArray.length){
            ia[startTmp++]=tmpArray[tmpIndexWhrite++];
        }
    }
    //归并排序20220530END
    //快速排序20200230START
    public static void main(String[] args){
        int[] ia ={5,4,6,7,3,2,1,0};

        fastSortT(ia,0,7);
        fastSortT(ia,0,7);

    }
    //递归
    public static void fastSortT(int[] ia,int start,int end){
        int index = pureSortT(ia,start,end);
        if(index-start>=2){
            fastSortT(ia,start,index-1);
        }
        if(end-index>=2){
            fastSortT(ia,index+1,end);
        }
    }
    //排序
    public static int pureSortT(int[] ia,int start,int end){
        //以第一个数为基准数，挖出来
        int base = ia[start];
        int beforeIndex = start+1;
        int afterIndex = end;
        int pit = start;
        //从后往前且前后指针不碰撞，找比基准数小的数，找到后挖出来填到上一个坑中，
        //从前往后且前后指针不碰撞，找比基准数大的数，找到后挖出来填到上一个坑中，
        while(beforeIndex<=afterIndex){
            while (beforeIndex<=afterIndex&&ia[afterIndex]>base){
                afterIndex--;
            }
            if(beforeIndex<=afterIndex){
                ia[pit] = ia[afterIndex];
                pit = afterIndex;

            }
            while(beforeIndex<=afterIndex&&ia[beforeIndex]<base){
                beforeIndex++;
            }
            if(beforeIndex<=afterIndex){
                ia[pit] = ia[beforeIndex];
                pit = beforeIndex;
            }
        }

        //将基准数填回留下的坑中
        ia[pit] = base;
        return pit;
    }
    //快排序20200530END






}
